<!DOCTYPE html>
<html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-0 vector-toc-not-available vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-0 skin-theme-clientpref-day vector-sticky-header-enabled" lang="de" dir="ltr"><head>
<meta charset="UTF-8">
<title>EXPTIME</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="icon" type="image/png" href="./_res_/favicon.png">
<link rel="canonical" href="https://de.wikipedia.org/wiki/EXPTIME"> <link href="./_mw_/ext.cite.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.math.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.wikimediamessages.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link href="./_mw_/ext.gadget.citeRef.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.defaultPlainlinks.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonHide.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonLayout.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonStyle.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiDarkmode.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiResponsive.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.specialSearch.css" rel="stylesheet" type="text/css">
<link rel="stylesheet" type="text/css" href="./_mw_/site.styles.css">
<link rel="stylesheet" type="text/css" href="./_mw_/noscript.css">
<link rel="stylesheet" type="text/css" href="./_res_/footer.css">
<link rel="stylesheet" type="text/css" href="./_res_/vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-EXPTIME rootpage-EXPTIME skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">EXPTIME</span></h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="contentSub">
<div id="mw-content-subtitle"></div>
</div>
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">
<p>In der <a href="Komplexit%C3%A4tstheorie" title="Komplexitätstheorie">Komplexitätstheorie</a> steht <b>EXPTIME</b> (manchmal auch nur <b>EXP</b>) für die <a href="Komplexit%C3%A4tsklasse" title="Komplexitätsklasse">Komplexitätsklasse</a> der <a href="Entscheidbar" class="mw-redirect" title="Entscheidbar">Entscheidungsprobleme</a>, die von einer <a href="Determinismus_(Algorithmus)" title="Determinismus (Algorithmus)">deterministischen</a> <a href="Turingmaschine" title="Turingmaschine">Turingmaschine</a> (DTM) in durch <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}\left(2^{p(n)}\right)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">O</mi>
</mrow>
</mrow>
<mrow>
<mo>(</mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>p</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
</mrow>
</msup>
<mo>)</mo>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left(2^{p(n)}\right)}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cf6840a6655e7f3245f4ca1800bbe0681534c00f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:9.5ex; height:4.843ex;" alt="{\displaystyle {\mathcal {O}}\left(2^{p(n)}\right)}" loading="lazy"></span> beschränkter <a href="Zeitkomplexit%C3%A4t" title="Zeitkomplexität">Zeit</a> entschieden werden können. <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p\left(n\right)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>p</mi>
<mrow>
<mo>(</mo>
<mi>n</mi>
<mo>)</mo>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle p\left(n\right)}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3481bd469c9ef55643f31049e4fe7ccd89ad6b99.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:4.85ex; height:2.843ex;" alt="{\displaystyle p\left(n\right)}" loading="lazy"></span> ist dabei ein beliebiges <a href="Polynom" title="Polynom">Polynom</a> in der Eingabelänge <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span>. In der <a href="DTIME" title="DTIME">DTIME</a>-Notation ausgedrückt gilt also:
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mbox{EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}\left(2^{n^{k}}\right).}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="false" scriptlevel="0">
<mtext>EXPTIME</mtext>
</mstyle>
</mrow>
<mo>=</mo>
<munder>
<mo>⋃<!-- ⋃ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
<mo>∈<!-- ∈ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">N</mi>
</mrow>
</mrow>
</munder>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="false" scriptlevel="0">
<mtext>DTIME</mtext>
</mstyle>
</mrow>
<mrow>
<mo>(</mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
</mrow>
</msup>
</mrow>
</msup>
<mo>)</mo>
</mrow>
<mo>.</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mbox{EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}\left(2^{n^{k}}\right).}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7841aa8aec69ea8266100439cfe56b80a8fc1918.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:33.209ex; height:6.176ex;" alt="{\displaystyle {\mbox{EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}\left(2^{n^{k}}\right).}" loading="lazy"></span></dd></dl>
<div class="mw-heading mw-heading2"><h2 id="EXPTIME-Vollständigkeit"><span id="EXPTIME-Vollst.C3.A4ndigkeit"></span>EXPTIME-Vollständigkeit</h2></div>
<p>Ein Problem ist EXPTIME-vollständig, wenn es in EXPTIME ist und jedes Problem in EXPTIME in Polynomialzeit auf dieses zurückgeführt werden kann (<a href="Polynomialzeitreduktion" title="Polynomialzeitreduktion">Polynomialzeitreduktion</a>). Während die Frage der Gleichheit von P und NP ein berühmtes offenes Problem der Informatik ist (<a href="P-NP-Problem" title="P-NP-Problem">P-NP-Problem</a>, speziell ob <a href="NP-Vollst%C3%A4ndigkeit" title="NP-Vollständigkeit">NP-vollständige</a> Probleme in P liegen), ist bei EXPTIME-vollständigen Problemen bekannt, dass sie nicht in P liegen. Das folgt auch aus dem <a href="Komplexit%C3%A4tstheorie" title="Komplexitätstheorie">Zeithierarchiesatz</a>.
</p><p>Ein Beispiel ist eine Variante des Halteproblems für deterministische Turingmaschinen, zu entscheiden ob diese bei gegebenem Input in höchstens k Schritten hält. Die Sprache <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {L}}=\{\langle M,x,k\rangle \mid M{\mbox{ ist eine DTM, die bei Eingabe }}x\mathrm {\ nach\ h{\ddot {o}}chstens\ } k\mathrm {\ Schritten\ h{\ddot {a}}lt} \}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">L</mi>
</mrow>
</mrow>
<mo>=</mo>
<mo fence="false" stretchy="false">{</mo>
<mo fence="false" stretchy="false">⟨<!-- ⟨ --></mo>
<mi>M</mi>
<mo>,</mo>
<mi>x</mi>
<mo>,</mo>
<mi>k</mi>
<mo fence="false" stretchy="false">⟩<!-- ⟩ --></mo>
<mo>∣<!-- ∣ --></mo>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="false" scriptlevel="0">
<mtext> ist eine DTM, die bei Eingabe </mtext>
</mstyle>
</mrow>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mtext> </mtext>
<mi mathvariant="normal">n</mi>
<mi mathvariant="normal">a</mi>
<mi mathvariant="normal">c</mi>
<mi mathvariant="normal">h</mi>
<mtext> </mtext>
<mi mathvariant="normal">h</mi>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mover>
<mi mathvariant="normal">o</mi>
<mo>¨<!-- ¨ --></mo>
</mover>
</mrow>
</mrow>
<mi mathvariant="normal">c</mi>
<mi mathvariant="normal">h</mi>
<mi mathvariant="normal">s</mi>
<mi mathvariant="normal">t</mi>
<mi mathvariant="normal">e</mi>
<mi mathvariant="normal">n</mi>
<mi mathvariant="normal">s</mi>
<mtext> </mtext>
</mrow>
<mi>k</mi>
<mrow class="MJX-TeXAtom-ORD">
<mtext> </mtext>
<mi mathvariant="normal">S</mi>
<mi mathvariant="normal">c</mi>
<mi mathvariant="normal">h</mi>
<mi mathvariant="normal">r</mi>
<mi mathvariant="normal">i</mi>
<mi mathvariant="normal">t</mi>
<mi mathvariant="normal">t</mi>
<mi mathvariant="normal">e</mi>
<mi mathvariant="normal">n</mi>
<mtext> </mtext>
<mi mathvariant="normal">h</mi>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mover>
<mi mathvariant="normal">a</mi>
<mo>¨<!-- ¨ --></mo>
</mover>
</mrow>
</mrow>
<mi mathvariant="normal">l</mi>
<mi mathvariant="normal">t</mi>
</mrow>
<mo fence="false" stretchy="false">}</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {L}}=\{\langle M,x,k\rangle \mid M{\mbox{ ist eine DTM, die bei Eingabe }}x\mathrm {\ nach\ h{\ddot {o}}chstens\ } k\mathrm {\ Schritten\ h{\ddot {a}}lt} \}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/affde027c10a7958b87defec4d7b69cedbb17188.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:84.533ex; height:2.843ex;" alt="{\displaystyle {\mathcal {L}}=\{\langle M,x,k\rangle \mid M{\mbox{ ist eine DTM, die bei Eingabe }}x\mathrm {\ nach\ h{\ddot {o}}chstens\ } k\mathrm {\ Schritten\ h{\ddot {a}}lt} \}}" loading="lazy"></span> ist ein Beispiel für eine EXPTIME-vollständige Sprache und das erwähnte <a href="Halteproblem" title="Halteproblem">Halteproblem</a> entspricht dem <a href="Wortproblem_(Berechenbarkeitstheorie)" title="Wortproblem (Berechenbarkeitstheorie)">Wortproblem</a> in dieser Sprache.<sup id="cite_ref-CS21_1-0" class="reference"><a href="#cite_note-CS21-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Der Grund für die EXPTIME-Schwierigkeit liegt intuitiv darin, dass die Zahl <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> exponentiell größer ist als die Länge ihrer Kodierung (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log k}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>log</mi>
<mo><!-- --></mo>
<mi>k</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \log k}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b6da5ed161853319a3a48f3c479cd0339bc5bded.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.57ex; height:2.509ex;" alt="{\displaystyle \log k}" loading="lazy"></span> bits), und es zum Entscheiden, ob <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>M</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle M}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"></span> auf <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>x</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle x}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> nach höchstens <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> Schritten hält, im Allgemeinen keine effizientere Möglichkeit gibt, als <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>M</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle M}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"></span> auf <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>x</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle x}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> für <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> Schritte zu simulieren.
</p>
<div class="mw-heading mw-heading3"><h3 id="Beispiele_für_EXPTIME-vollständige_Probleme"><span id="Beispiele_f.C3.BCr_EXPTIME-vollst.C3.A4ndige_Probleme"></span>Beispiele für EXPTIME-vollständige Probleme</h3></div>
<p>Mehrere Beispiele für EXPTIME-vollständige Probleme sind Zweipersonenspiele. Die konkrete Fragestellung ist, ob ein Spieler aus einer gegebenen Spielposition
eine Strategie hat, um das Spiel sicher zu gewinnen. Beispiele für EXPTIME-vollständige Spiele sind
</p>
<ul><li>verallgemeinertes Schach (auf einem n x n Brett für beliebig hohe n, die erforderliche Zeit wächst exponentiell mit n)<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup></li>
<li>Dame<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup></li>
<li>Go mit den japanischen Ko-Regeln<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup></li></ul>
<p>Alle diese Spiele haben die Eigenschaft gemeinsam, dass ein Spiel exponentiell viele Züge haben kann. Spiele, die nur polynomiell viele Züge pro Spiel erlauben und bei denen
eine Spielposition polynomiell beschrieben werden, können in <a href="PSPACE" title="PSPACE">PSPACE</a> gelöst werden.
</p><p>Eine andere Quelle für EXPTIME-vollständige sind Graph-Probleme, bei denen die Eingabe durch einen kompakten Schaltkreis repräsentiert wird.
Dieser Schaltkreis kann exponentiell kleiner sein als eine explizite Repräsentation des Graphen.
Da die Komplexität im Verhältnis zur Eingabegröße angegeben wird, sind viele Probleme, die mit
einer expliziten Repräsentation <a href="P_(Komplexit%C3%A4tsklasse)" title="P (Komplexitätsklasse)">P</a>-vollständig sind, bei der Schaltkreis-Repräsentation EXPTIME-vollständig.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>
<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>
</p>
<div class="mw-heading mw-heading2"><h2 id="Beziehung_zu_anderen_Komplexitätsklassen"><span id="Beziehung_zu_anderen_Komplexit.C3.A4tsklassen"></span>Beziehung zu anderen Komplexitätsklassen</h2></div>
<p>Die folgenden Beziehungen sind bekannt:
</p>
<dl><dd><a href="NC_(Komplexit%C3%A4tsklasse)" title="NC (Komplexitätsklasse)">NC</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \subseteq }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo>⊆<!-- ⊆ --></mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \subseteq }</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a924f8dcb2847bb8871edfdbf4c6b5cca0669228.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \subseteq }" loading="lazy"></span> <a href="P_(Komplexit%C3%A4tsklasse)" title="P (Komplexitätsklasse)">P</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \subseteq }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo>⊆<!-- ⊆ --></mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \subseteq }</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a924f8dcb2847bb8871edfdbf4c6b5cca0669228.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \subseteq }" loading="lazy"></span> <a href="NP_(Komplexit%C3%A4tsklasse)" title="NP (Komplexitätsklasse)">NP</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \subseteq }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo>⊆<!-- ⊆ --></mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \subseteq }</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a924f8dcb2847bb8871edfdbf4c6b5cca0669228.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \subseteq }" loading="lazy"></span> <a href="PSPACE" title="PSPACE">PSPACE</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \subseteq }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo>⊆<!-- ⊆ --></mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \subseteq }</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a924f8dcb2847bb8871edfdbf4c6b5cca0669228.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \subseteq }" loading="lazy"></span> EXPTIME <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \subseteq }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo>⊆<!-- ⊆ --></mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \subseteq }</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a924f8dcb2847bb8871edfdbf4c6b5cca0669228.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \subseteq }" loading="lazy"></span> <a href="NEXPTIME" title="NEXPTIME">NEXPTIME</a></dd></dl>
<p>Da P nach dem <a href="Komplexit%C3%A4tstheorie#Zeithierarchiesatz" title="Komplexitätstheorie">Zeithierarchiesatz</a> eine echte <a href="Teilmenge" title="Teilmenge">Teilmenge</a> von EXPTIME ist, muss mindestens eine der Teilmengenbeziehungen <a href="P_(Komplexit%C3%A4tsklasse)" title="P (Komplexitätsklasse)">P</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \subseteq }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo>⊆<!-- ⊆ --></mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \subseteq }</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a924f8dcb2847bb8871edfdbf4c6b5cca0669228.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \subseteq }" loading="lazy"></span> <a href="NP_(Komplexit%C3%A4tsklasse)" title="NP (Komplexitätsklasse)">NP</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \subseteq }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo>⊆<!-- ⊆ --></mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \subseteq }</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a924f8dcb2847bb8871edfdbf4c6b5cca0669228.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \subseteq }" loading="lazy"></span> <a href="PSPACE" title="PSPACE">PSPACE</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \subseteq }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo>⊆<!-- ⊆ --></mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \subseteq }</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a924f8dcb2847bb8871edfdbf4c6b5cca0669228.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \subseteq }" loading="lazy"></span> EXPTIME echt sein. Es wird vermutet, dass alle Inklusionen echt sind.
</p>
<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>
<ol class="references">
<li id="cite_note-CS21-1"><span class="mw-cite-backlink"><a href="#cite_ref-CS21_1-0">↑</a></span> <span class="reference-text">Chris Umans: <i>CS21: Decidability and Tractability, <a rel="nofollow" class="external text" href="http://users.cms.caltech.edu/~umans/cs21/lec18.pdf">Lecture 18</a> (PDF; 133 kB)</i></span>
</li>
<li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a></span> <span class="reference-text">Aviezri Fraenkel, D. Lichtenstein, Computing a perfect strategy for n×n chess requires time exponential in n, J. Comb. Th. A, Band 31, 1981, S. 199–214.</span>
</li>
<li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a></span> <span class="reference-text">J. M. Robson, N by N checkers is Exptime complete, SIAM Journal on Computing, Band 13, 1984, S. 252–267</span>
</li>
<li id="cite_note-4"><span class="mw-cite-backlink"><a href="#cite_ref-4">↑</a></span> <span class="reference-text">J. M. Robson, The complexity of Go, Information Processing; Proceedings of IFIP Congress. 1983, S. 413–417.</span>
</li>
<li id="cite_note-5"><span class="mw-cite-backlink"><a href="#cite_ref-5">↑</a></span> <span class="reference-text"><span class="book">Christos H. Papadimitriou: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Computational Complexity</cite>. 1995, A Glimpse Beyond, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>491–508</span> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abookitem&rfr_id=info:sid/de.wikipedia.org:EXPTIME&rft.atitle=A+Glimpse+Beyond&rft.au=Christos+H.+Papadimitriou&rft.btitle=Computational+Complexity&rft.date=1995&rft.genre=bookitem&rft.pages=491-508" style="display:none"> </span></span></span>
</li>
<li id="cite_note-6"><span class="mw-cite-backlink"><a href="#cite_ref-6">↑</a></span> <span class="reference-text">José L. Balcázar, Antoni Lozano, Jacobo Torán: <cite class="lang" lang="en" dir="auto" style="font-style:italic">The complexity of algorithmic problems on succinct instances.</cite> In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Computer Science</cite>. 1992, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1007/978-1-4615-3422-8_30">10.1007/978-1-4615-3422-8_30</a></span> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:EXPTIME&rft.atitle=The+complexity+of+algorithmic+problems+on+succinct+instances.&rft.au=Jos%C3%A9+L.+Balc%C3%A1zar%2C+Antoni+Lozano%2C+Jacobo+Tor%C3%A1n&rft.btitle=Computer+Science&rft.date=1992&rft.doi=10.1007%2F978-1-4615-3422-8_30&rft.genre=book" style="display:none"> </span></span>
</li>
</ol>
<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>
<ul><li><i><a rel="nofollow" class="external text" href="https://complexityzoo.net/Complexity_Zoo:E#exp">EXPTIME</a>.</i> In: <i>Complexity Zoo.</i> (englisch)</li></ul></div><!--htdig_noindex--><div><div class="zim-footer">
Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-05-25" href="https://de.wikipedia.org/wiki/?title=EXPTIME&oldid=256327510">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
<script src="./_webp_/webpHandler.js"></script>
</body></html>